package main

import (
	//"container/heap"
	//"data-structure/sortedList"
	//"fmt"
	//"sort"
	"data-structure/LRU"
)

//import "data-structure/tree"

func main() {
	//list := sortedList.New()
	//list.Insert(3)
	//list.Insert(2)
	//list.Insert(6)
	//list.Insert(9)
	//list.Insert(8)
	//list.PrintAll()
	//list.Delete(6)
	//list.PrintAll()
	//list.Delete(2)
	//list.PrintAll()
	//
	//demoTree := &tree.TreeNode{
	//	Val: 1,
	//	LeftChild: &tree.TreeNode{
	//		Val: 2,
	//		LeftChild: &tree.TreeNode{
	//			Val: 4,
	//		},
	//		RightChild: &tree.TreeNode{
	//			Val: 5,
	//		},
	//	},
	//	RightChild: &tree.TreeNode{
	//		Val: 3,
	//		LeftChild: &tree.TreeNode{
	//			Val: 6,
	//		},
	//		RightChild: &tree.TreeNode{
	//			Val: 7,
	//		},
	//	},
	//}
	//tree.PreOrderTraversal(demoTree)
	//
	//tree.InOrderTraversal(demoTree)
	//tree.PostOrderTraversal(demoTree)
	//
	//input := []int{22, 34, 5, 6, 7, 0, 11, 33, 2}
	////input := []int{22, 34}
	//fsort(input)
	//avl := tree.InitAVL(input)
	//tree.LevelOrder(avl.Head)
	//avl.Insert(10)
	//avl.Insert(12)
	//avl.Insert(13)
	//avl.Insert(14)
	//tree.LevelOrder(avl.Head)
	//fmt.Println(avl.Find(22))
	//
	//h := &IntHeap{100, 16, 4, 8, 70, 2, 36, 22, 5, 12}
	//fmt.Println("\nHeap")
	//heap.Init(h)
	//fmt.Printf("min: %d", (*h)[0])
	//
	//fmt.Println("\nHeap sort:")
	//for h.Len() > 0 {
	//	fmt.Printf("%d ", heap.Pop(h))
	//}
	//fmt.Println("\nPush(h, 3),然后输出堆看看:")
	//heap.Push(h, 3)
	//for h.Len() > 0 {
	//	fmt.Printf("%d ", heap.Pop(h))
	//}
	//
	//fmt.Println("\n使用sort.Sort排序:")
	//h2 := IntHeap{100, 16, 4, 8, 70, 2, 36, 22, 5, 12}
	//sort.Sort(h2)
	//for _, v := range h2 {
	//	fmt.Printf("%d ", v)
	//}
	cache := LRU.NewLRUCache(3)
	cache.Put(1, 1)
	cache.Put(2, 2)
	cache.Put(3, 3)
	cache.PrintAll()
	cache.Get(1)
	cache.PrintAll()
	cache.Put(5, 5)
	cache.PrintAll()
	cache.Get(3)
	cache.PrintAll()

}

func fsort(input []int) {
	if len(input) <= 1 {
		return
	}
	mid := input[0]
	left, right := 1, len(input)-1
	for left <= right {
		for ; left <= right && input[left] < mid; left++ {
		}
		for ; left <= right && input[right] >= mid; right-- {
		}
		//此时left和right必定不相等，
		if left < right {
			input[left], input[right] = input[right], input[left]
			left++
			right--
		}
	}
	input[right], input[0] = input[0], input[right]
	//right min = 0
	//left max = len(input)
	fsort(input[:right])
	fsort(input[left:])
}

type IntHeap []int

func (h IntHeap) Len() int {
	return len(h)
}

func (h IntHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h IntHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}
